package org.example.Soution003;

import java.util.*;

public class HeapKthRelease {
    public static void main(String[] args) {
        HeapKthRelease heap = new HeapKthRelease();
        int[] arr = {1,1,1,3,3,2};
        int[] res=heap.topKFrequent(arr,2);
        System.out.println(Arrays.toString(res));
    }


    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        int length = map.size();
        Set<Map.Entry<Integer,Integer>> set = map.entrySet();
        List<Map.Entry<Integer,Integer>> list=new ArrayList<Map.Entry<Integer,Integer>>(set);
        int[] res = new int[k];
        //快排
        quickSort(list,0,length-1,res,0,k);
        return res;
    }

    public void quickSort(List<Map.Entry<Integer,Integer>> list,int start,int end,int[] res,int resIndex,int k){
        int picked=(int)(Math.random()*(end-start+1)+start);
        Collections.swap(list,picked,start);
        int flag=list.get(start).getValue();
        int index=start;
        for(int i=start+1;i<=end;i++){
            if(list.get(i).getValue()>=flag){
                Collections.swap(list,index+1,i);
                index++;
            }
        }
        Collections.swap(list,index,start);

        //判断
        if(k<=index-start){
            quickSort(list,start,index-1,res,resIndex,k);
        }else{
            //左边全是符合条件的
            for(int i=start;i<=index;i++){
                res[resIndex++]=list.get(i).getKey();
            }
            //再看看需不需要再往右边找找
            if(k>index-start+1) quickSort(list,index+1,end,res,resIndex,k-(index-start+1));
        }
    }
}
